#include<iostream>
#include<vector>
#include<string>
#include<utility>
#include<queue>
using namespace std;


typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<vector<bool>> check;
int m = 0;
int n = 0;


//733.图像渲染
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color){
    //先获取需要修改的像素值
    int cur = image[sr][sc];
    //如果要修改的像素值就等于目标值
    if(cur==color){
        return image;
    }

    //创建一个队列，队列中存放到是一个键值对，表示二维下标
    queue<PII> q;
    //起始位置入队
    q.push({sr, sc});

    while(!q.empty()){
        //获取队头元素
        auto [a, b] = q.front();
        q.pop();
        //将当前位置修改成目标值
        image[a][b] = color;

        //四个方向搜索将符合条件的下标入队
        for (int i = 0; i < 4; i++){
            int x = a + dx[i], y = b + dy[i];
            if(x>=0&&x<image.size()&&y>=0&&y<image[0].size()&&image[x][y]==cur){
                q.push({x, y});
            }
        }
    }

    //返回修改后的数组
    return image;
}

//200.岛屿数量
int ret = 0;
void bfs(vector<vector<char>>& grid,int i,int j){
    //创建一个队列，将起始位置入队
    queue<PII> q;
    q.push({i, j});
    check[i][j] = true;

    while(!q.empty()){
        //获取队头元素的下标
        auto [a,b]=q.front();
        q.pop();

        //搜索四个方向的下标，将符合条件的入队
        for (int k = 0; k < 4; k++){
            int x = a + dx[k], y = b + dy[k];
            if(x>=0&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&check[x][y]==false){
                //将当前位置标记为已搜索
                //这里是一个注意点，需要入队的同时标记为已搜索，而不是先入队等出队的时候再标记为已搜索
                //因为先入队等出队再标记会导致一些位置重复入队，时间复杂度增大，部分情况会导致超时
                //这里需要特别注意
                check[a][b] = true;
                q.push({x, y});
            }
        }
    }
}
int numIslands(vector<vector<char>>& grid){
    //获取行数和列数
    m=grid.size();
    n = grid[0].size();
    //先初始化布尔类型的二维数组
    check.resize(m, vector<bool>(n));

    // 遍历原始数组，找到每个岛屿的起始位置
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if (grid[i][j] == '1' && check[i][j] == false){
                // 找到岛屿起始位置，通过广度搜索将连通块标记为已搜索
                bfs(grid, i, j);
                // 搜索一次，就是找到一个岛屿，数量加一
                ret++;
            }
        }
    }

    return ret;
}

//695.岛屿的最大面积
int maxnum = 0;
int bfs(vector<vector<int>>& grid,int i,int j){
    //创建一个队列
    queue<PII> q;
    //起始位置入队，并标记已搜索
    q.push({i, j});
    check[i][j] = true;

    int num = 1;

    while(!q.empty()){
        //获取队头下标
        auto [a,b]=q.front();
        q.pop();

        //搜索四个方向，将符合条件的下标入队
        for (int k = 0; k < 4; k++){
            int x = a + dx[k], y = b + dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&check[x][y]==false){
                check[x][y] = true;
                num++;
                q.push({x, y});
            }
        }
    }

    return num;
}
int maxAreaOfIsland(vector<vector<int>>& grid){
    //获取行数和列数
    m = grid.size();
    n = grid[0].size();
    //初始化布尔类型的二维数组
    check.resize(m, vector<bool>(n));

    //遍历数组，找到每个岛屿的起始位置
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(grid[i][j]==1&&check[i][j]==false){
                int num=bfs(grid, i, j);
                maxnum = max(maxnum, num);
            }
        }
    }

    return maxnum;
}

//130.被围绕的区域
void bfs(vector<vector<char>>& board,int i,int j){
    //创建一个队列，并将起始位置入队，修改成'.'
    queue<PII> q;
    q.push({i, j});
    board[i][j] = '.';

    while(!q.empty()){
        //获取队头下标
        auto [a, b] = q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int x = a + bx[k], y = b + by[k];
            if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O'){
                board[x][y] = '.';
                q.push({x, y});
            }
        }
    }
}
void solve(vector<vector<char>>& board){
    m = board.size();
    n = board[0].size();
    //正难则反思想
    //将第一行和最后一行遍历，遇到'O'就广度搜索周边位置，将连通块中的'O'全都修改成'.'
    for (int j = 0; j < n; j++){
        if(board[0][j]=='O'){
            bfs(board, 0, j);
        }
        if(board[m-1][j]=='O'){
            bfs(board, m - 1, j);
        }
    }

    //将第一列和最后一列遍历，遇到'O'就广度搜索周边位置，将连通块中的'O'全都修改成'.'
    for (int i = 0; i < m; i++){
        if(boar[i][0]=='O'){
            bfs(board, i, 0);
        }
        if(board[i][n-1]=='O'){
            bfs(board, i, n - 1);
        }
    }

    //遍历整个原始数组，遇到'O'修改成'X',遇到'.'修改成'O'
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(board[i][j]=='O'){
                board[i][j] = 'X';
            }
            if(board[i][j]=='.'){
                board[i][j] = 'O';
            }
        }
    }
}

int main(){

    return 0;
}